/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Chemin;


import java.util.List;

/**
 *
 * @author okaido
 */
public class PathFindingAStart{

    private LinkedListSpe listeOuverte = new LinkedListSpe(); /// Liste de cases répertoriée et pas encore analysées
    private LinkedListSpe listeFermee = new LinkedListSpe(); /// Liste de case analysées
    private Coordonnee coordonneeArrive;
    private boolean tabOuverte[][] = new boolean[this.nbCaseX][this.nbCaseY];
    private boolean tabFermee[][] = new boolean[this.nbCaseX][this.nbCaseY];
    private Case tabIt[][] = new Case[this.nbCaseX][this.nbCaseY];
    private int nbCaseX;
    private int nbCaseY;
    private int stop; // a delete
    // private final int tabVoisinX[] = {0, 1, 1, 1, 0, -1, -1, -1};
    // private static final int tabVoisinY[] = {1, 1, 0, -1, -1, -1, 0, 1};
    private final int tabVoisinX[][] = {{-1, -1, -1, 0, 0, 1, 1, 1},
        {-1, 0, -1, 1, -1, 1, 0, 1},
        {0, -1, 1, -1, 1, -1, 1, 0},
        {1, 0, 1, -1, 1, -1, 0, -1},
        {1, 1, 1, 0, 0, -1, -1, -1},
        {1, 0, 1, -1, 1, -1, 0, -1},
        {0, -1, 1, -1, 1, -1, 1, 0},
        {-1, 0, -1, 1, -1, 1, 0, 1}};
    private final int tabVoisinY[][] = {
        {0, -1, 1, -1, 1, -1, 1, 0},
        {-1, -1, 0, -1, 1, 0, 1, 1},
        {-1, -1, -1, 0, 0, 1, 1, 1},
        {-1, -1, 0, -1, 1, 0, 1, 1}, 
        {0, -1, 1, -1, 1, -1, 1, 0},
        {1, 1, 0, 1, -1, 0, -1, -1},
        {1, 1, 1, 0, 0, -1, -1, -1},
        {1, 1, 0, 1, -1, 0, -1, -1}};
    private final int tabVoisinCout[][] = {
        {10, 14, 14, 10, 10, 14, 14, 10},
        {14, 10, 10, 14, 14, 10, 10, 14},
        {10, 14, 14, 10, 10, 14, 14, 10},
        {14, 10, 10, 14, 14, 10, 10, 14},
        {10, 14, 14, 10, 10, 14, 14, 10},
        {14, 10, 10, 14, 14, 10, 10, 14},
        {10, 14, 14, 10, 10, 14, 14, 10},
        {14, 10, 10, 14, 14, 10, 10, 14}};
    private final int tabDirection[][] = {
        {4, 5, 3, 6, 2, 7, 1, 0},
        {5, 6, 4, 7, 3, 0, 2, 1},
        {6, 5, 7, 4, 0, 3, 1, 2},
        {7, 6, 0, 5, 1, 4, 2, 3},
        {0, 7, 1, 6, 2, 5, 3, 4},
        {1, 2, 0, 3, 7, 4, 6, 5},
        {2, 3, 1, 4, 0, 5, 7, 6},
        {3, 2, 4, 1, 5, 0, 6, 7}};

    public PathFindingAStart(int nbCaseX, int nbCaseY) {
        this.nbCaseX = nbCaseX;
        this.nbCaseY = nbCaseY;
        this.stop = 0; ///xxx - a delete
    }

    public void calculPath(Coordonnee depart, Coordonnee dest, List<Coordonnee> listPath, int tabMap[][]) {
        int H, Htemp;
        Case result;
        this.coordonneeArrive = dest; // Coordonnée d'arrivée

        for (int i = 0; i < this.nbCaseX; i++) {
            for (int j = 0; j < this.nbCaseY; j++) {
                this.tabOuverte[i][j] = false;
                this.tabFermee[i][j] = false;
            }
        }
        this.listeOuverte.removeAll();
        this.listeFermee.removeAll();

        // Distance a vol d'oiseau (Mahatan) pour la case de depard
        H = depart.getX() - this.coordonneeArrive.getX();
        if (H < 0) {
            H = -H;
        }
        Htemp = depart.getY() - this.coordonneeArrive.getY();
        if (Htemp >= 0) {
            H += Htemp;
        } else {
            H += -Htemp;
        }
        H = H * 10;

        this.listeOuverte.push_front(new Case(depart, H, 0, H, 0, null)); // Case Initiale
        this.tabOuverte[depart.getX()][depart.getY()] = true;
        this.tabIt[depart.getX()][depart.getY()] = this.listeOuverte.getFirst();

        result = this.calculPathGen(tabMap);//,0);
        if (result == null) {
            System.out.println("result = null");
        } else {
            System.out.println("(" + result.getCoordonnee().getX() + "," + result.getCoordonnee().getY() + ")");
        }
        this.ecriturePath(listPath, result);
    }

    Case calculPathGen(int tabMap[][]) {//, int direction) {
        int x, y, xc, yc, i, F, G, H, Htemp, Fc, Gc, Hc;// numTabVoisin;
        int direction;
        Case it, result;
        Case caseTemp, caseTemp2;
        //list<Case *>::iterator result;
        stop++;
        System.out.println("* " + stop);
        if (stop == 1500) {
            return null;
        }
        //x = itCourant->getCoordonnee().getX();
        //y = itCourant->getCoordonnee().getY();

        if (this.listeOuverte.getSize() == 0) {
            System.out.println("Pas de chemin possible, on improvise");
            // Recherche de la Case avec le F minimale dans la list listeFermee. Return minIt;
            int minF, courantF;
            Case minIt;
            it = this.listeFermee.getFirst();
            minF = it.getH();
            minIt = it;
            //it.next();
            for (it= it.getSucc(); it != null;it = it.getSucc()) { //
                courantF = it.getH();
                if (courantF < minF) {
                    minF = courantF;
                    minIt = it;
                }
            }
            return minIt;
        } else {
            // === Recherche du la Case avec le F minimale dans la list ouverte. Return minIt;
            Case pCase = this.listeOuverte.getFirst(); // on prend le F minimum du tableau trié.
            this.listeOuverte.pop_front();
            this.tabOuverte[pCase.getCoordonnee().getX()][pCase.getCoordonnee().getY()] = false;
            this.listeFermee.push_front(pCase);
            this.tabFermee[pCase.getCoordonnee().getX()][pCase.getCoordonnee().getY()] = true;

            x = pCase.getCoordonnee().getX();
            y = pCase.getCoordonnee().getY();
            F = pCase.getF();
            G = pCase.getG();
            H = pCase.getH();

            //  +++++++

            //cout << "x : " << x << "  y : " << y << endl;

            // Condition d'arret
            if ((x == this.coordonneeArrive.getX()) && (y == this.coordonneeArrive.getY())) {
                System.out.println("YOUPI");
                return pCase;
            } else {
                // Coeur du traitement
                // === Enumeration des voisins
                //switch(case)
                //numTabVoisin = 3;

                // === Traitement des voisins

                direction = pCase.getDirection();
                for (i = 0; i < 8; i++) {
                    xc = x + tabVoisinX[direction][i];
                    yc = y + tabVoisinY[direction][i];
                    if ((xc >= 0) && (xc < this.nbCaseX) && (yc >= 0) && (yc < this.nbCaseY)) {
                        if (tabMap[xc][yc] == 1) { // Detection des obstacles
                            //cout << "On a un Mur" << endl;
                        } else {
                            if (this.tabFermee[xc][yc] == false) { // Detection si la case est dans la liste Fermée
                                if (this.tabOuverte[xc][yc] == true) { // Detection si la case est dans la liste Ouverte


                                    it = this.tabIt[xc][yc];
                                    caseTemp = it;

                                    // Recalcule du G et donc du F, la distance parcouru
                                    Gc = G + tabVoisinCout[direction][i];

                                    if (caseTemp.getG() > Gc) {
                                        caseTemp.setG(Gc);
                                        Fc = Gc + caseTemp.getH();
                                        caseTemp.setF(Fc);
                                        caseTemp.setParent(pCase);
                                        caseTemp.setDirection(tabDirection[direction][i]);
                                        // === Réinsertion ordonnée ==
                                        Case it2;
                                        for (it2 = this.listeOuverte.getFirst(); it2 != null; it2 = it2.getSucc()) {
                                            if (it2.getF() > Fc) {
                                                this.listeOuverte.insert(it2,it);
                                                this.tabIt[xc][yc] = it2;
                                                break;
                                            }
                                        }
                                        if (it2 == null) {
                                            this.listeOuverte.push_back(it);
                                            this.tabIt[xc][yc] = this.listeOuverte.getLast();
                                        }

                                        // === Supression du noeud non ordonné
                                        this.listeOuverte.remove(it);
                                    }
                                } else if (tabMap[xc][yc] != 1) {

                                    // === Calcul des F=G+H
                                    // Distance parcouru
                                    Gc = G + tabVoisinCout[direction][i];

                                    // Distance a vole d'oiseau de mahattan

                                    Hc = xc - this.coordonneeArrive.getX();
                                    if (Hc < 0) {
                                        Hc = -Hc;
                                    }
                                    Htemp = yc - this.coordonneeArrive.getY();
                                    if (Htemp >= 0) {
                                        Hc += Htemp;
                                    } else {
                                        Hc += -Htemp;
                                    }
                                    Hc = Hc * 10;

                                    // Distance total
                                    Fc = Gc + Hc;

                                    // === Insertion ordonnée:
                                    Case it2;
                                    for (it2 = this.listeOuverte.getFirst(); it2 != null; it2 = it2.getSucc()) {

                                        if (it2.getF() > Fc) {
                                            caseTemp = new Case(new Coordonnee(xc, yc), Fc, Gc, Hc, tabDirection[direction][i], pCase);
                                            //it = this.listeOuverte.insert(it2, new Case(new Coordonnee(xc, yc), Fc, Gc, Hc, tabDirection[direction][i], pCase));
                                            this.listeOuverte.insert(it2, caseTemp);


                                            this.tabOuverte[xc][yc] = true;
                                            this.tabIt[xc][yc] = caseTemp;
                                            break;
                                        }
                                    }
                                    if (it2 == null) {
                                        this.listeOuverte.push_back(new Case(new Coordonnee(xc, yc), Fc, Gc, Hc, tabDirection[direction][i], pCase));
                                        this.tabOuverte[xc][yc] = true;
                                        this.tabIt[xc][yc] = this.listeOuverte.getLast();
                                    }

                                }

                            }


                        }
                    }
                }
                return (this.calculPathGen(tabMap));
            }
        }
    }

    /**
     * Creation du chemin de l'unité vers la première destination
     */
    private void ecriturePath(List<Coordonnee> listPath, Case caseDest) {
        Case caseDebut = this.listeFermee.getFirst();
        if (caseDest != null) {
            while (caseDest != caseDebut) {
                listPath.add(0, caseDest.getCoordonnee());
                caseDest = caseDest.getParent();
            }
        } else {
            System.out.println("Ecriture path = NULL");
        }

    }
}
